package com.zyk.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zhangsan
 * @date 2021/4/5 16:50
 */
public class J61 {

    // https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/
    // 暴力解
    static public boolean isStraight(int[] nums) {
        // 1-5 张牌
        // 有重复牌返回false
        // 在不包含重复元素的情况下,最大值减最小值小于5 就是顺子
        Set<Integer> set = new HashSet<>();
        int max = 0, min = 14;
        for (int num : nums) {
            if(num == 0) continue;
            if(set.contains(num)) return false;
            set.add(num);
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        return max - min < 5;
    }

    static public boolean isStraight2(int[] nums) {
        // 插入排序+计算
        for (int i = 1; i < nums.length; i++) {
            int j = i;
            while (j > 0) {
                if(nums[j] == nums[j-1] && nums[j] != 0) {
                    // 包含重复元素
                    return false;
                }else if(nums[j] < nums[j-1]) {
                    nums[j-1] = nums[j] ^ nums[j-1];
                    nums[j]   = nums[j] ^ nums[j-1];
                    nums[j-1] = nums[j] ^ nums[j-1];
                    j--;
                }else {
                    break;
                }
            }
        }
        int min = 0;
        for (; min < nums.length; min++) {
            if(nums[min] != 0) {
                break;
            }
        }
        return nums[4] - nums[min] < 5;
    }

    // for test
    public static void main(String[] args) {
        int[] nums = {10,11,0,12,6};
        System.out.println(isStraight(nums));
        System.out.println(isStraight2(nums));
    }

}
